package normal.哈希表.链式地址哈希表;

import normal.哈希表.基于列表实现.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ZhuYi
 * @create 2025/2/17 13:59
 * <p>
 * 哈希冲突--链式地址哈希表
 */
public class HashMapChaining {
    int size;//键值对数量
    int capacity;//哈希表容量
    double loadThres;//负载因子阈值
    int extendRatio;//扩容倍数
    List<List<Pair>> buckets;//桶数组

    //构造方法
    public HashMapChaining() {
        size = 0;
        capacity = 4;
        loadThres = 2.0 / 3.0;
        extendRatio = 2;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    //哈希函数
    int hashFunc(int key) {
        return key % capacity;
    }

    //负载因子
    double loadFactor() {
        return (double) size / capacity;
    }

    //查询操作
    String getVal(int key) {
        //获取索引
        int index = hashFunc(key);
        //获取节点
        List<Pair> pairs = buckets.get(index);
        //遍历节点
        for (Pair pair : pairs) {
            if (pair.key == key) {
                return pair.val;
            }
        }
        return null;
    }

    //添加
    void put(int key, String val) {
        //当负载因子超过阈值时，执行扩容
        if (loadFactor() > loadThres) {
            extend();
        }
        int index = hashFunc(key);
        List<Pair> pairs = buckets.get(index);
        //遍历节点，若遇到key，则更新val
        for (Pair pair : pairs) {
            if (pair.key == key) {
                pair.val = val;
                return;
            }
        }
        //若没有遇到key,则添加到队尾
        pairs.add(new Pair(key, val));
        size++;
    }

    //删除
    void remove(int key) {
        int index = hashFunc(key);
        List<Pair> bucket = buckets.get(index);
        //遍历桶，删除键值对
        for (Pair pair : bucket) {
            if (pair.key == key) {
                bucket.remove(pair);
                size--;
                break;
            }
        }
    }


    //扩容哈希表
    void extend() {
        //暂存原哈希表
        List<List<Pair>> hashTmp = buckets;
        //初始化扩容后的哈希表
        capacity *= extendRatio;
        buckets = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());
        }
        size = 0;
        //搬运
        for (List<Pair> bucket : hashTmp) {
            for (Pair pair : bucket) {
                put(pair.key, pair.val);
            }
        }
    }

    //打印哈希表
    void print() {
        for (List<Pair> bucket : buckets) {
            List<String> res = new ArrayList<>();
            for (Pair pair : bucket) {
                res.add(pair.key + " -> " + pair.val);
            }
            System.out.println(res);
        }
    }

}
